The present invention claims priority from Japanese Patent Applications No.11-015872 filed Jan. 25, 1999, No.11-015877 filed Jan. 25, 1999, No.11-096940 filed Apr. 2, 1999, No.11-096945 filed Apr. 2, 1999 and No.11-098101 filed Apr. 5, 1999, the contents of which are incorporated herein by reference.
1. Field of the Invention
This invention can be utilized for a push service which copies and distributes content to a plurality of destinations. In this specification, xe2x80x9cpush servicexe2x80x9d signifies a service which copies and distributes, to a plurality of user terminals, a packet sent by an information providing terminal, wherein the information providing terminal can transfer packets at a regular interval or at a prescribed time without knowing the state of the user terminals. Users can operate the user terminals whenever they wish and can extract the information that has been distributed.
2. Description of Related Art
FIGS. 44, 45 and 46 serve to explain the configuration of a conventional datagram network, indicating respectively the configuration of a conventional packet, a conventional network and a conventional multicast packet. The network shown in FIG. 45 has router 30 which has routing table 20, and when a packet with address DA as shown in FIG. 44 is sent into the network from a source, router 30 passes this packet if the address in question is downstream of the router.
There is only one such address in the network and if it is desired to send the packet to a plurality of addresses, a plurality of copies of the packet are formed as indicated in FIG. 46, and these are sent within the network after respective addresses have been added (DA1, DA4, . . . , DA7).
It is anticipated that future multimedia networks will see an increase in push services and that this will be accompanied by an increase in traffic comprising packets being multicast to a plurality of destinations. Networks of the sort described hitherto will not be able to deal with this situation efficiently. Push services have recently been increasing on the Internet as well, and content ranging from weather forecasts to the latest technical news is now being automatically distributed. However, this kind of service cannot operate efficiently over point-to-point networks that use conventional unique addresses.
For example, a packet sent from a source has to be copied and the addresses of a plurality of destinations have to be respectively added to the copied packets. In other words, it is necessary to generate a large number of packets to which as many different addresses as there are destinations have been added, and it takes time to generate such packets.
Moreover, in a situation where the destinations to which a packet is to be distributed are not fixed but are constantly changing, it is difficult for the source to ascertain these changes in real time, with the result that a packet may be generated for an address that has already been released. Alternatively, it may be impossible to generate a packet for a newly added address.
Another consequence can be that information which users did not request is distributed, or that information with the desired content is not distributed at all. Because information with undesired content will end up being deleted by users without being utilized, such information constitutes redundant traffic for the distribution network.
Given this background technology, it is an object of this invention to provide a push network capable of generating, by simple means, packets for use in a push service. It is a further object of this invention to provide a push network capable of responding in real time to changes in the addresses to which a packet is to be distributed. It is yet another object of this invention to provide a push network which ensures that only information with content and/or of a category which users desire is distributed. A further object of the invention is to provide a push network capable of efficiently transferring push service traffic. Yet another object of this invention is to provide a push network capable of making effective use of the memory resources in each node of a distribution network.
The principal distinguishing features of this invention are as follows. Firstly, it adds to a packet a content identifier for identifying the content, or, if a category to which the content belongs can be identified, one or both of a content identifier and a category identifier for identifying the category to which the content belongs. Secondly, a user registers in advance in the distribution network content identifier related information, or one or both of content identifier related information and category identifier related information, said information relating to the content and/or category which the user wishes to receive. Thirdly, the distribution network has content filters, or one or both of content filters and category filters, which pass packets with content, or with one or both of content and categories, wanted by a downstream user. This invention differs from the prior art in that the user sets the packet format, how the filter table is used, and the identifiers corresponding to the required content and/or category.
Namely, this invention is a push network comprising means for copying information held in a packet sent from an information providing terminal and for generating a plurality of packets with the same information, and means for distributing the packets thereby generated to a plurality of user terminals.
The distinguishing features of this invention are that it provides means for adding to a packet a content identifier for identifying the content of the information held in that packet, or for adding one or both of this content identifier and a category identifier for identifying the category to which the content belongs; and that the aforementioned distributing means comprises means for deciding, in accordance with the aforementioned content identifier, or in accordance with one or both of the aforementioned content identifier and category identifier, whether or not to distribute that packet to a given user terminal.
For example, means can be provided for adding a content identifier to a packet, and the distributing means can comprise means for deciding, in accordance with the content identifier, whether or not to distribute that packet to a given user terminal.
In this case, the decision means preferably includes a table, provided in correspondence with a destination, in which content identifier related information has been registered; and means for passing a packet if the content identifier added to that packet matches the content identifier related information registered in the table.
Means is preferably provided for registering content identifier related information in this table in accordance with notification from a user.
The result of these provisions is that it is not necessary to add, to each of a plurality of multicast packets, a respective and separate destination identifier uniquely assigned within the distribution network. Instead, it is sufficient to add the same identifier to the plurality of multicast packets, this identifier serving to identify the content of that packet, thereby simplifying the packet generation procedure.
Because the user constituting the destination can himself register in the table content identifier related information, the distribution network can recognize the content required by the user, so that transfer of useless packets can be avoided. As a result, increase in traffic is suppressed. Moreover, because the user does not receive useless packets, received information can be processed efficiently. Furthermore, because the user registers content in the distribution network, even if the situation of a user constituting a destination is constantly changing, the source can still distribute content without having to be aware of these changes.
It follows that use of a push network according to this invention enables push service traffic to be transferred efficiently.
A content identifier that has been registered in the table but which has become unnecessary is preferably deleted.
Namely, means is preferably provided for deleting from the table content identifier related information registered in the table, once a series of packets to which that content identifier has been added have passed. This ensures that a content identifier that has become unnecessary does not remain in the table indefinitely, and that memory resources can be utilized effectively.
The aforementioned deleting means can alternatively comprise means for deleting the aforementioned content identifier related information from the table after a prescribed time interval has elapsed after the series of packets have passed. This ensures that if, after a series of packets having the same content identifier have passed, yet another packet with the same content identifier is generated, this further packet can be passed, provided a fixed time interval is not exceeded.
The deleting means can alternatively comprise means for deleting from the table, at a predetermined time, content identifier related information registered in the table.
This ensures that a content identifier relating to content which becomes invalid at a certain time can be deleted irrespective of whether or not there is a packet, thereby enabling effective utilization of memory resources. Moreover, if a packet is erroneously transferred at a time when the information has already become invalid, then because the content identifier is deleted at a certain time, transfer of invalid packets can be avoided.
The aforementioned decision means can alternatively comprise means for receiving a packet requesting deletion of content identifier related information, and for deleting the corresponding content identifier related information from the aforementioned table. In this case, the aforementioned user terminal or information providing terminal preferably comprises means for transmitting a packet requesting deletion of the aforementioned content identifier related information.
For example, information relating to the route from an information providing terminal to a user can be written in a packet arriving at that user, and means can be provided whereby that user sends a packet requesting deletion of content identifier related information in accordance with this routing information; and a node having an aforementioned table can comprise means for receiving this packet requesting deletion and for deleting from the table the corresponding content identifier related information. This ensures that if there is content regarding which distribution had been desired but which has become unnecessary, the user can delete the corresponding content identifier related information from the table by notifying the distribution network to this effect.
Content identifier related information can thus be deleted at the discretion of a user or of an information provider. The distribution of content which has become unnecessary can therefore be made to stop by the user. Moreover, if there is a destination which wishes to prohibit distribution of information, the information provider can implement this by deleting content identifier related information corresponding to that destination.
The aforementioned decision means can alternatively comprise means which, if no packet having the same content identifier as that of passed packets arrives within a fixed time interval after the final packet has passed, deletes from the table the information relating to that content identifier. This ensures that each node can autonomously detect content whereof distribution has already been completed, and can delete the corresponding content identifier related information from the table.
Alternatively, the decision means can comprise means for deleting content identifier related information from the table when it receives a packet giving notification that receiving has been completed, said packet having been sent from a node or user that has received packets to which the corresponding content identifier has been added. This makes it possible to confirm that a packet has reached its destination before deleting the corresponding content identifier related information, thereby avoiding the situation where content identifier related information is erroneously deleted from a table before a packet has reached its destination.
The aforementioned registering means preferably comprises means for receiving a request packet in which has been written a content identifier relating to content desired by a user, and means for registering content identifier related information in the aforementioned table in accordance with the content identifier written in the request packet received by this receiving means.
This mechanism enables content which a user desires to be registered in the distribution network. Because the distribution network only has to distribute content required by the user, push service traffic can be efficiently transferred.
One registering means can be provided for a plurality of decision means. In this case, the registering means preferably comprises: means for storing, in correspondence with content, information indicative of the information providing terminal constituting the source of packets with that content; means for searching for a route from that information providing terminal to a given user terminal in accordance with the stored contents of this storage means; and means which, in accordance with the result of the search conducted by this searching means, registers content identifier related information notified by a user, in the tables of the decision means along the route in question.
Thus, in order to register, in the table of each decision means, content identifier related information notified by a user, it is necessary to search for a route from the information providing terminal in question to the user terminal in question, and to register, in the tables of the nodes on that route, the content identifier related information notified by the user. This invention stores, in correspondence with content, information indicative of the information providing terminal constituting the source of packets with that content, and searches for a route on the basis of this.
Alternatively, a separate registering means can be provided for each decision means. In this case, the registering means preferably comprises: means for storing, in correspondence with content, information indicative of the information providing terminal constituting the source of packets with that content; means for searching, in accordance with the stored contents of this storage means, for a route from that information providing terminal to a given user terminal; and means for transferring an arriving request packet in accordance with information, written in that request packet, regarding the route to the information providing terminal. This transferring means preferably includes means which, when there is no information in an arriving request packet regarding the route to the information providing terminal, writes said information in that request packet, in accordance with the routing information found by the search means.
Thus, if a large number of registering means are provided in non-centralized fashion, then for example the node which first receives a request packet searches for a route from the-information providing terminal in question to the user terminal in question and writes routing information in the request packet. Once the routing information has been written, it is no longer necessary for subsequent nodes to conduct a route search. Instead, they can simply transfer the request packet in accordance with this routing information.
The registering means can alternatively comprise: means for storing, in correspondence with content, information indicative of the information providing terminal constituting the source of packets with that content; means for searching, in accordance with the stored contents of this storage means, for a route to the information providing terminal written in an arriving request packet; and means which, in accordance with the results of the search by this search means, updates the routing information in the aforementioned request packet. If a route search is conducted each time a request packet arrives at a node, then even if an unsuitable route has been found by a node downstream from the information providing terminal, the routing information can be modified by subsequent upstream nodes. For example, if a transmission line fault occurs in the distribution network while a request packet is being transferred, it is possible that the route found by the node nearest the user terminal will already have become an unsuitable route. Under such circumstances, a suitable route can always be selected by updating the routing information at each node.
The registering means can comprise means for storing, in correspondence with information relating to the address of an information providing terminal, said information having been written in an arriving request packet, information relating to an output port to be used for routing.
If this is done, each node must hold routing information for transferring packets to the next node, but does not have to hold information relating to the topology of the entire distribution network, and therefore the amount of information held by each node can be decreased.
The registering means can alternatively comprise: means for sending an arriving request packet to all output routes connected to the local node (i.e., the node containing the registering means); means for writing in a request packet information relating to the sending history of this sending means; means for detecting, in accordance with this sending history information, the number of hops made by the request packet; and means which, when the same packet arrives from a plurality of routes, selects one of these packets in accordance with the result obtained by this detection means.
This makes it unnecessary for each node to hold full information, such as information on the topology of the entire distribution network, or even routing information up to the next node. If a plurality of the same request packets arrive, then for example the packet having the fewest number of hops can be selected.
There can also be provided means for temporarily storing a packet which the decision means has decided to distribute. This temporary storage means preferably comprises means for temporarily storing a packet to be transferred to a transfer destination when the packet acceptance rate of that packet transfer destination is less than a prescribed rate.
Namely, by providing means for temporarily storing a packet at a transit node and storing a packet in this temporary storage means when a packet transfer destination is experiencing decreased throughput, a decrease in throughput at transit nodes upstream of the site of throughput decrease can be avoided.
Thus, by providing means for temporarily storing a packet which it has been decided to distribute, if throughput decreases at a location in the distribution network, a packet to be transferred to this location is stored by the temporary storage means when it has reached the immediately preceding location in the distribution network. Consequently, a packet can be transferred at locations upstream of the location where throughput has decreased without being affected by this decrease in throughput, thereby ensuring that a decrease in throughput at some distribution destinations does not affect the entire distribution network.
If there are a plurality of information providing terminals, it is also preferable to provide means which causes a token to circulate among these terminals, this token giving permission to an information providing terminal to send; and to provide means which causes content to be sent from the information providing terminal that has received the token.
This ensures that collision of packets sent from the plurality of information providing terminals is avoided.
Transit nodes can be arranged hierarchically between information providing terminals and user terminals, with a plurality of information providing terminals or transit nodes provided in each layer of this hierarchy. In this case, each layer of the hierarchy can comprise: means for collecting traffic information for that hierarchical layer; means which gives sending permission to the plurality of information providing terminals and/or transit nodes in accordance with the traffic information collected by this collecting means; and means which causes content to be sent from the information providing terminal and/or transit node that has received sending permission.
This ensures that collision of packets sent from a plurality of information providing terminals or transit nodes is avoided, and that packets are transferred in accordance with the traffic situation. For example, control can be implemented whereby packet transfer from an information providing terminal or transit node experiencing downstream traffic congestion can be avoided, and whereby packet transfer from an information providing terminal or transit node with relatively little downstream traffic is given preference.
In the examples given so far, a push network according to this invention has been implemented using only content identifiers. Examples will now be given in which a push network according to this invention is implemented using one or both of content identifiers and category identifiers.
Namely, means can be provided for adding to a packet a content identifier for identifying the content of the information held in that packet, and a category identifier for identifying the category to which that content belongs; and the aforementioned distributing means can comprise means for deciding, in accordance with this content identifier and/or category identifier, whether or not to distribute that packet to a given user terminal.
In this case, the aforementioned decision means preferably includes a table, provided in correspondence with a destination, in which has been registered information relating to the aforementioned category identifier and/or to the aforementioned content identifier corresponding to this category identifier; and also preferably includes means which passes a packet if the category identifier given to that packet matches the category identifier related information registered in this table, and if the content identifier given to the packet matches the content identifier related information registered in the table in correspondence with this category identifier.
Means can alternatively be provided for registering in the aforementioned table, in accordance with notification from a user, information relating to a content identifier and/or a category identifier corresponding to information content which that user wishes to receive, or to information content which the user wishes to reject. Alternatively, means can be provided for registering in the aforementioned table, in correspondence with a destination and in accordance with notification from an information provider, information relating to a content identifier and/or a category identifier corresponding to information content which that information provider wishes to distribute or to prohibit from being distributed.
Namely, this invention adds to a packet one or both of a content identifier and a category identifier for identifying the content and category of the information in that packet, and the user (i.e., the destination) registers in the distribution network in advance information relating to a content identifier and/or a category identifier corresponding to information content which that user wishes to receive or wishes to reject. Because each node in the distribution network has a filter which passes a packet when it contains information with content and/or of a category which a downstream user requires, transfer of unwanted packets to a user can be avoided.
This ensures that no packet of a specified category can pass, or conversely, that a packet of a specified category can pass unconditionally. A user is thus able to select a packet to be sent to the user by category as well as by content. This enables a user to perform finer filtering than when using content alone to select what packets are sent. Alternatively, by registering in the table only category identifier related information and setting the condition that content is not to be taken into consideration, a user can broaden the range of information that is selected. Moreover, the distribution network can implement efficient filtering by performing content-based filtering once rough filtering has been carried out by means of a category.
Instead of adding an individual user address to each separate packet, by simply adding to a packet a content identifier and/or a category identifier, an information provider can distribute a packet to a user who requires packets with that content and/or of that category.
Alternatively, by ensuring that an information provider can register in advance in the distribution network a content identifier and/or a category identifier corresponding to information content which that information provider wishes to distributexe2x80x94or which it prohibits from being distributedxe2x80x94to specific destinations, the information provider can proactively distribute to specific users information with specific content and/or of a specific category, or can prohibit the distribution of that information to specific users.
The configuration of the means for deleting information relating to a content identifier and/or a category identifier that has been registered in the table, and the configuration of the means for registering such information, are similar to the configurations, described above, when just a content identifier is used. Namely, the means for deleting information can comprise means for deleting from the table information relating to a content identifier and/or a category identifier, once a series of packets containing that content identifier and/or category identifier have passed. This deleting means can alternatively comprise means for deleting from the table information relating to a content identifier and/or a category identifier after a prescribed time interval has elapsed after the aforementioned series of packets have passed, or it can comprise means for deleting from the table, at a predetermined time, information relating to a content identifier and/or a category identifier registered in the table. Alternatively, the decision means can comprise means for receiving a packet requesting deletion of information relating to a content identifier and/or a category identifier, and for deleting the corresponding information from the aforementioned table.
In this case, a user terminal can comprise means for transmitting a packet requesting deletion of information relating to a content identifier and/or a category identifier, or an information providing terminal can comprise means for transmitting a packet requesting deletion of information relating to a content identifier and/or a category identifier.
The aforementioned decision means can alternatively comprise means which, if no packet having the same content identifier and/or category identifier as passed packets arrives within a fixed time interval after the final packet has passed, deletes from the table the information relating to that content identifier and/or category identifier. Alternatively, the decision means can comprise means for deleting from the table information relating to a content identifier and/or a category identifier when it receives a packet giving notification that receiving has been completed, said packet having been sent from a node or user terminal that has received packets with the corresponding content identifier and/or category identifier.
The aforementioned registering means can comprise means for receiving a request packet in which has been written a content identifier and/or a category identifier notified by a user, and means for registering content identifier and/or category identifier related information in the aforementioned table in accordance with the content identifier and/or category identifier written in the request packet received by this receiving means. One registering means can be provided for a plurality of decision means. In this case, the registering means comprises: means for storing, in correspondence with content and/or category, information indicative of the information providing terminal constituting the source of packets with that content and/or of that category; means for searching for a route from that information providing terminal to a given user terminal in accordance with the stored contents of this storage means; and means which, in accordance with the result of the search conducted by this searching means, registers content identifier and/or category identifier related information notified by a user, in the tables of the decision means along the route in question.
Alternatively, a separate registering means can be provided for each decision means. In this case, the registering means can comprise: means for storing, in correspondence with content and/or category, information indicative of the information providing terminal constituting the source of packets with this content and/or of this category; means for searching, in accordance with the stored contents of this storage means, for a route from that information providing terminal to a given user terminal; and means for-transferring an arriving request packet in accordance with information, written in the request packet, regarding the route to the information providing terminal. This transferring means includes means which, when there is no information in an arriving request packet regarding the route to the information providing terminal, writes said information in that request packet, in accordance with the routing information found by the search means. The registering means can alternatively comprise: means for storing, in correspondence with content and/or category, information indicative of the information providing terminal constituting the source of packets with that content and/or of that category; means for searching, in accordance with the stored contents of this storage means, for a route to the information providing terminal written in an arriving request packet; and means which, in accordance with the result of the search by this search means, updates the routing information in the aforementioned request packet. The registering means can alternatively comprise means for storing, in correspondence with information relating to the address of an information providing terminal, said information having been written in an arriving request packet, information relating to an output port to be used for routing. The registering means can alternatively comprise: means for sending an arriving request packet to all output routes connected to the local node; means for writing in a request packet information relating to the sending history of this sending means; means for detecting, in accordance with this sending history information, the number of hops made by the request packet; and means which, when the same packet arrives from a plurality of routes, selects one of these packets in accordance with the results obtained by this detection means.
The examples described above have used either content identifiers alone, or both content identifiers and category identifiers. However, examples using category identifiers alone could also be considered. Such examples could be described in a similar way by simply replacing the terms xe2x80x9ccontentxe2x80x9d and xe2x80x9ccontent identifierxe2x80x9d in the previously given descriptions of examples using content identifiers alone with the terms xe2x80x9ccategoryxe2x80x9d and xe2x80x9ccategory identifierxe2x80x9d.
As has been described above, this invention is capable of generating, by simple means, packets for use in a push service. It is also capable of responding in real time to changes in the addresses to which a packet is to be distributed. Moreover, it ensures that only information with content and/or of a category which users desire is distributed. It is therefore capable of efficiently transferring push service traffic. It is also capable of making effective use of the memory resources in each node of a distribution network.